#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <string.h>

#include "abb.h"
#include "nodo_arbol.h"

/************************************************
*	Definicion de los tipos de datos	*
************************************************/

struct abb{
	nodo_arbol_t* root;
	size_t cantidad_nodos;
	abb_comparar_clave_t comparar_dato;
	abb_destruir_dato_t destruir_dato;
};

/************************************************
*		Primivivas del ABB		*
************************************************/

abb_t* abb_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato)
{
	abb_t* arbol = malloc(sizeof(abb_t));

	if(!arbol)
        return NULL;

	arbol->root = NULL;

	arbol->cantidad_nodos = 0;

	arbol->comparar_dato = cmp;

	arbol->destruir_dato = destruir_dato;

	return arbol;
}

bool abb_ordenado(const abb_t* arbol)
{
	return nodos_ordenados(arbol->root,arbol->comparar_dato);
}

bool abb_guardar(abb_t *arbol, const char *clave, void *dato)
{
	nodo_arbol_t* nodo_encontrado = buscar_nodo(arbol->comparar_dato,arbol->root,clave);	
	if(nodo_encontrado == NULL)
	{
		nodo_arbol_t* nodo = nodo_crear(clave,dato);
		if(!nodo)
        		return false;

		//Si el arbol no tiene raiz, pongo el nodo como tal
    		if(arbol->root == NULL)
    		{
        		arbol->root = nodo;
        		arbol->cantidad_nodos +=1;
        		return true;
    		}

    		nodo_arbol_t *nodo_padre = buscar_nodo_padre(arbol->comparar_dato,NULL,arbol->root,nodo);

   	 	if(nodo_padre != NULL)
    		{	
			int cmp = nodo_comparar(nodo_padre,nodo,arbol->comparar_dato);
        		if(cmp < 0)
        		{
        		    nodo_agregar_hijo_der(nodo,nodo_ver_hijo_der(nodo_padre));
        		    nodo_agregar_hijo_der(nodo_padre,nodo);
        		    arbol->cantidad_nodos +=1;
        		}
			else
        		{	
				nodo_agregar_hijo_izq(nodo,nodo_ver_hijo_izq(nodo_padre));
            			nodo_agregar_hijo_izq(nodo_padre,nodo);
            			arbol->cantidad_nodos +=1;
        		}
    		}
	}
	else
	{	nodo_agregar_dato(nodo_encontrado,dato,arbol->destruir_dato);	}
    	return true;
}

bool abb_esta_vacio(abb_t *arbol)
{
    return (arbol->root == NULL);
}

void *abb_borrar(abb_t *arbol, const char *clave)
{
	void* dato = NULL;

	nodo_arbol_t* nodo = buscar_nodo(arbol->comparar_dato,arbol->root,clave);
	if(nodo != NULL)
	{

		dato = nodo_ver_dato(nodo);
		nodo_arbol_t* nodo_a_mover;

		bool cambiar_root = nodo == arbol->root;

		//Necesito mover los hijos
		if(!nodo_tiene_hijos(nodo))
		{
			nodo_arbol_t* nodo_padre = buscar_nodo_padre(arbol->comparar_dato,NULL,arbol->root,nodo);
			if(nodo_padre != NULL)
			{
				if(nodo_es_mayor(nodo_padre,nodo,arbol->comparar_dato))
				{	nodo_agregar_hijo_izq(nodo_padre,NULL);	}
				else
				{	nodo_agregar_hijo_der(nodo_padre,NULL);	}
			}

			nodo_destruir_sin_dato(nodo);

			if(cambiar_root)
				arbol->root = NULL;
		}
		else
		{
			if(nodo_ver_hijo_izq(nodo) != NULL)
			{
				nodo_a_mover = buscar_maximo(nodo_ver_hijo_izq(nodo));
			}
			else
			{
				nodo_a_mover = buscar_minimo(nodo_ver_hijo_der(nodo));
			}

			nodo_arbol_t* padre = buscar_nodo_padre(arbol->comparar_dato,NULL,arbol->root,nodo_a_mover);

			if(padre != NULL)
			{
				if(nodo_tiene_hijos(nodo_a_mover))
				{
					if(padre != nodo)
					{
						if(nodo_es_mayor(padre,nodo_a_mover,arbol->comparar_dato))	//Estoy con el mas grande de la rama izq del nodo eliminado
						{
							nodo_agregar_hijo_izq(padre,nodo_ver_hijo_der(nodo_a_mover));
							if(nodo_ver_hijo_izq(nodo_a_mover) != NULL)
								printf("error al buscar menor\n");
						}
						else	//Estoy con el mas grande de los mas chicos del nodo eliminado
						{
							nodo_agregar_hijo_der(padre,nodo_ver_hijo_izq(nodo_a_mover));
							if(nodo_ver_hijo_der(nodo_a_mover) != NULL)
								printf("error al buscar mayor\n");
						}
					}
					else
					{
						if(nodo_es_mayor(padre,nodo_a_mover,arbol->comparar_dato))
						{
							nodo_agregar_hijo_izq(padre,nodo_ver_hijo_izq(nodo_a_mover));
						}
						else
						{
							nodo_agregar_hijo_der(padre,nodo_ver_hijo_der(nodo_a_mover));
						}
					}
				}
				else
				{
					if(nodo_es_mayor(padre,nodo_a_mover,arbol->comparar_dato))
					{
						nodo_agregar_hijo_izq(padre,NULL);
					}
					else
					{
						nodo_agregar_hijo_der(padre,NULL);
					}
				}
			}
			intercambiar_nodos(nodo,nodo_a_mover);

			nodo_destruir_sin_dato(nodo_a_mover);
		}

		arbol->cantidad_nodos -=1;
	}
	return dato;
}

void *abb_obtener(const abb_t *arbol, const char *clave)
{
	nodo_arbol_t* nodo_clave = buscar_nodo(arbol->comparar_dato,arbol->root,clave);
	if(nodo_clave != NULL)
		return nodo_ver_dato(nodo_clave);
	return NULL;

}

bool abb_pertenece(const abb_t *arbol, const char *clave)
{
	nodo_arbol_t* nodo_clave = buscar_nodo(arbol->comparar_dato,arbol->root,clave);
	if(nodo_clave != NULL)
		return true;
	return false;
}

size_t abb_cantidad(abb_t *arbol)
{
	return arbol->cantidad_nodos;
}

void abb_destruir(abb_t *arbol)
{
	if(arbol->root != NULL)
		nodo_destruir_en_cadena(arbol->root,arbol->destruir_dato);
	free(arbol);
}

/************************************************
*		Primivivas de iteración ABB		*
************************************************/

void abb_in_order(abb_t *arbol, bool visitar(const char *, void *, void *), void *extra)
{
    in_orden(arbol->root,visitar,extra);
}

abb_iter_t *abb_iter_in_crear(const abb_t *arbol)
{
    nodo_arbol_t *raiz = arbol->root;

    return nodo_iter_in_crear(raiz);
}

void abb_iter_in_destruir(abb_iter_t *iter)
{
    nodo_iter_in_destruir(iter);
    return;
}

const char *abb_iter_in_ver_actual(const abb_iter_t *iter)
{
    return nodo_iter_ver_actual(iter);
}

bool abb_iter_in_al_final(const abb_iter_t *iter)
{
    return nodo_iter_al_final(iter);
}

bool abb_iter_in_avanzar(abb_iter_t *iter)
{
    return nodo_iter_avanzar(iter);
}
